package leetcodecompetition.S110;

import CommonStructure.ListNode;

/**
 * @Author: Siantar
 * @Date: 2023-08-05-23:06
 * @Description: 1.0
 */
public class S6940 {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode tmp = head;
        while (tmp.next != null) {
            int v = gdc(tmp.val, tmp.next.val);
            ListNode mod = new ListNode(v);
            mod.next = tmp.next;
            tmp.next = mod;
            tmp = mod.next;
        }
        return head;
    }

    public int gdc(int a, int b) {
        if (b == 0) return a;
        int r = a % b;
        return gdc(b, r);
    }
}
